package test.algorithm.FastSlowPointer;

/**
 * 快慢指针
 * @author serenity
 *
 */
public class FastSlowPointer2 {

	public static void main(String[] args) {
		
		// 声明链表
		Node header = new FastSlowPointer2.Node(1);
		Node pointer = header;
		
		// 初始化循环链表
		for(int i=2;i<13;i++){
			pointer.next = new FastSlowPointer2.Node(i);
			pointer = pointer.next;
		}
		//设置循环链表
		pointer.next = header;
		printList(header);
		
		Node fast = header;
		Node slow = header;
		
		//快慢指针典型应用1 快速获取不定长链表中间节点的值
		while(true){
			
			if(fast.next!=null && fast.next.next!=null ){
				//快指针步长为2
				fast = fast.next.next;
				//慢指针步长为1
				slow = slow.next;
				if(fast.next==header || fast.next.next==header){
					break;
				}
			}else{
				//非循环链表，next为空即到链表末尾，跳出循环
				break;
			}
		}
		//慢指针的值就是链表中间值
		System.out.println("快指针的值："+fast.num);
		System.out.println("慢指针的值："+slow.num);
		
		//快慢指针典型应用2 判断链表是否循环链表
		fast = header;
		slow = header;
		while(true){
			
			if(fast.next!=null && fast.next.next!=null){
				//快指针步长为2
				fast = fast.next.next;
				//慢指针步长为1
				slow = slow.next;
				
				//原理：如果有环，快指针迟早都会与慢指针相遇。
				//（田径场赛跑，当快的领先慢的一圈时两者就会相遇）
				if(fast==slow){
					System.out.println("该链表是循环链表");
					break;
				}
			}else{
				//非循环链表，next为空即到链表末尾，跳出循环
				System.out.println("该链表不是循环链表");
				break;
			}
		}
	}
	
	/**
	 * 打印链表
	 * @param node
	 */
	static void printList(Node header){
		Node pointer = header;
		do{
			System.out.print(pointer.num+" ");
			pointer = pointer.next;
		}while(pointer!=null && pointer!=header);
		System.out.println();
	}
	
	
	static class Node{
		private int num;
		private Node next;
		
		public Node(int num){
			this.num=num;
		}
	}

}
